"""
767. 重构字符串
中等
相关标签
相关企业
提示
给定一个字符串 s ，检查是否能重新排布其中的字母，使得两相邻的字符不同。

返回 s 的任意可能的重新排列。若不可行，返回空字符串 "" 。



示例 1:

输入: s = "aab"
输出: "aba"
示例 2:

输入: s = "aaab"
输出: ""


提示:

1 <= s.length <= 500
s 只包含小写字母
"""
import heapq
from collections import Counter


class Solution:
    def reorganizeString(self, s: str) -> str:
        #  因为python没有最大堆的数据结构，只有最小堆的，所以我们存负数进去，取出负数里面最小的，去掉负号即为最大的
        maxHeap = [(-frq, chr) for chr, frq in Counter(s).items()]

        # 用于将一个列表转换成一个堆结构,原地转换,是以元组的第一个元素排序的
        heapq.heapify(maxHeap)
        newstr = ''
        while len(maxHeap) > 1:
            frq, chr = heapq.heappop(maxHeap)
            frq2, chr2 = heapq.heappop(maxHeap)
            newstr = newstr + chr + chr2
            # 拿出一个元素后检查是否有多的，若有多的就放回去。因为一开始加入的是负数。所以这里为+1而不是-1
            if frq + 1 != 0:
                heapq.heappush(maxHeap, (frq + 1, chr))
            if frq2 + 1 != 0:
                heapq.heappush(maxHeap, (frq2 + 1, chr2))
        #      <=1时不执行。当=1时，故加上最后一个,如果最后一个大于1则不可能形成左右各不相同。如果当=0时说明正好交替完
        if maxHeap:
            if maxHeap[0][0]<-1:
                return ''
            else:
                newstr += maxHeap[0][1]
        return newstr


if __name__ == '__main__':
    print(Solution().reorganizeString("abbabbaaab"))
